Ітераційні методи розв`язання систем лінійних алгебраїчних рівнянь

Введення
Ця курсова робота включає в себе три ітераційних методу рішення систем лінійних алгебраїчних рівнянь (СЛАР):
1. Метод Якобі (метод ітерацій).
2. Метод Холецкого.
3. Метод верхньої релаксації.
Також дана курсова робота включає в себе: опис методу, застосування методу для конкретної задачі (аналіз), код програми вирішення перерахованих вище методів на мові програмування Borland C + + Builder 6.

Опис методу
Метод рішення задачі називають ітераційним, якщо в результаті отримують нескінченну послідовність наближень до рішення. Основна перевага ітераційних методів полягає в тому, що точність шуканого рішення задається. Число ітерацій, яке необхідно виконати для отримання заданої точності , Є основною оцінкою якості методу. З цього числа проводиться порівняння різних методів.
Головним недоліком цих методів є те, що питання збіжності ітераційного процесу вимагає окремого дослідження. Прикладом звичайних ітераційних методів служать: метод ітерацій (метод Якобі), метод Зейделя, метод верхніх релаксацій.
Почнемо з методу ітерацій або як його ще називають методу Якобі.
Існує сіcтема A · x = f (1), де матриця A = [a _ij] (i, j = 1, 2, ... m) має зворотну матрицю; x = (x _1, x _2, x _3, ... x _m ) - вектор невідомих, f - вектор вільних членів. Систему (1) потрібно перетворити до наступного вигляду: (2) i = 1, 2, ..., m, де , , При цьому aii 0.
Значення суми вважається рівним 0, якщо верхня межа підсумовування менше нижнього. Тоді при i = 1 рівняння має вигляд: (3). У методі Якобі виходять із запису системи у вигляді (2), ітерації при цьому визначають наступним чином: , (N = 0, 1, ..., n0, i = 1, 2, ..., m) (4).
Початкові значення - (I = 0, 1, ..., m) задаються довільно (у програмі ми це робимо, вводячи функцію по генерації випадкових чисел - «random»). Закінчення ітераційного процесу визначають або завданням максимального числа ітерацій n _0, або наступною умовою: , Де > 0. В якості нульового наближення в системі (4) приймемо .
Якщо послідовність наближень x ₁ ^(0), x ₂ ^(0), ..., x _m ^(0), x ^{_{1 (1),}} x ₂ ^(1), ..., x _m ^(1), ..., x ₁ ^(k) , x ₂ ^(k), ..., x _m ^(k) має межу , , То ця межа є рішенням системи (2).
Достатньою умовою збіжності рішення системи (1) є те, що матриця A є матрицею з переважаючими діагональними елементами, тобто , I = 1, 2, ..., m.
Тепер розглянемо другий ітераційний метод - метод Зейделя, який є модифікацією методу Якобі. Основна його ідея полягає в тому, що при обчисленні (k +1) - го наближення невідомої x _i враховуються вже обчислені раніше (k +1) - ті наближення (x ₁ x _2, ..., x _i-1).
Нехай дана наведена лінійна система: (I = 1, 2, ... n) (5). Вибираються довільно початкові наближення коренів x ₁ ^(0), x ₂ ^(0), ..., x _n ^(0), щоб вони в якійсь мірі відповідали невідомим x _1, x _2, x _3, ..., x _n.
Передбачається, що k-е наближення коренів відомо, тоді відповідно до ідеї методу будується (k +1) - ті наближення за наступними формулами:

	k = 0,1,2, ... (6)

Якщо виконується достатня умова збіжності для системи (5) - по рядках, то в методі Зейделя вигідно розташувати рівняння (6) так, щоб перше рівняння системи мало найменшу суму модулів коефіцієнтів: .
Тепер розглянемо 3 метод - метод верхніх релаксацій.
Метод верхньої релаксації - це є метод Зейделя із заданим числовим параметром w.
Одним з найбільш поширених однокрокових методів є метод верхніх релаксацій, який має наступний вигляд (7), де w заданий числовий параметр (0 <w <2). Змінюючи w можна отримувати різну швидкість збіжності ітераційного процесу. Цей параметр вибирається таким чином, щоб на кожному кроці ітераційного процесу зменшувалася величина, що характеризує близькість отриманого рішення до шуканого розв'язку системи.
Перевагою ітераційного методу верхніх релаксацій є те, що при його реалізації програмним шляхом алгоритм обчислень має простий вигляд і дозволяє використовувати всього один масив для невідомого вектора.
Для отримання розрахункових формул (7) перепишемо у вигляді: або в компонентній запису отримаємо (8) - це є основна обчислювальна формула.
У вираз (8) і входять однаковим чином => при обчисленнях вони можуть бути записані в один і той же масив. При реалізації методу верхніх релаксацій використовується наступна форма запису алгоритму обчислень .
Дійсно, при послідовному знаходженні елемента (I +10 ітерації) на кожному кроці будуть використовуватися знайдені раніше значення, які при k <j відповідають i +1 ітерації, а при k <ji ітерації.
Застосування методу до конкретного завдання (аналіз)
Складаючи завдання на мові програмування Borland C + + Builder 6 для реалізації точних методів розв'язання СЛАР я враховував різну кількість рівнянь в системі (розмірність матриці ставив рівним nxn). Але для перевірки результатів використовував систему рівнянь:

Взагалі кажучи, процес Зейделя сходиться швидше, ніж метод Якобі. Буває, що процес Зейделя сходиться, коли проста ітерація розходиться і т.п. Правда, буває і навпаки. У всякому разі, достатні умови збіжності для методу Якобі достатні і для збіжності методу Зейделя. Реалізувавши програми з одержаної відповіді я побачив, що процес Зейделя сходиться швидше. Це видно за кількістю ітерацій отриманих в програмі при наближеною точності = 0,000001. Якщо для методу Якобі вони становлять 16, то для методу Зейделя вони становлять 9.
Також розглядаючи метод верхньої релаксації і порівнюючи його з двома іншими методами видно, що в методі верхньої релаксації кількість ітерацій залежить від заданого числового параметра w. Задаючи w = 1, кількість ітерацій дорівнює 9, зменшуючи значення параметра від 1 кількість ітерацій починає рости, у свою чергу збільшуючи параметр кількість ітерацій теж починає зростати.
Наведемо таблицю показують кількість ітерацій (k) при різних значеннях параметра w:

w	0.1	0.4	0.8	0.9	1	1.1	1.2	1.3	1.7	1.9
k	16	15	14	13	9	13	14	15	16	16

З усього цього можна зробити висновок, що ітераційні методи сходяться швидше, ніж точні методи, про що свідчать як швидке зменшення нев'язок, так і зменшення змін невідомих.
Лістинг програми
/ / -
# Include <vcl. H>
# Pragma hdrstop
# Include «Unit1.h»
/ / -
# Pragma package (smart_init)
# Pragma resource «*. dfm»
# Include <math.h>
# Include <stdlib.h>
TForm1 * Form1;
int n = 0, prov = 0, k = 0;
const x = 100;
float A [x] [x], B [x] [x];
float C [x], Y [x];
float * X;
bool fl1 = false;
float e;
float v_sh;
/ / -
__fastcall TForm1: TForm1 (TComponent * Owner)
: TForm (Owner)
{
}
/ / -
void __fastcall TForm1: ButtonOkClick (TObject * Sender)
{
Memo1-> Lines-> Clear ();
k = 0;
TryStrToInt (Edit1-> Text, n);
if (n> 1)
{
StringGrid1-> Enabled = true;
StringGrid1-> RowCount = n;
StringGrid1-> ColCount = n +1;
ButtonClear-> Enabled = true;
ButtonOk-> Enabled = false;
StringGrid1-> Color = clWindow;
ButtonYakobi-> Enabled = true;
ButtonZeydel-> Enabled = true;
ButtonRelax-> Enabled = true;
X = new float [n];
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
A [i] [j] = NULL;
}
X [i] = NULL;
}
}
else
{
ShowMessage («Число повинно бути дійсного типу!");
}
}
/ / -
void __fastcall TForm1: ButtonClearClick (TObject * Sender)
{
StringGrid1-> Enabled = false;
StringGrid1-> RowCount = 0;
StringGrid1-> ColCount = 0;
ButtonClear-> Enabled = false;
ButtonOk-> Enabled = true;
StringGrid1-> Color = clBtnFace;
ButtonYakobi-> Enabled = false;
}
/ / -
void __fastcall TForm1: ButtonYakobiClick (TObject * Sender)
{
/ / TryStrToFloat (Edit2-> Text, e);
Memo1-> Lines-> Clear ();
e = StrToFloat (Edit2-> Text);
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
TryStrToFloat (StringGrid1-> Cells [j] [i], A [i] [j]);
}
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
if (A [i] [j] == NULL)
{
ShowMessage («Помилка! Є порожні клітинки!");
fl1 = true;
i = n;
break;
}
}
}
if (! fl1) {
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
if (i! = j) B [i] [j] = (-1) * A [i] [j] / A [i] [i];
else
{
B [i] [j] = 0;
C [i] = A [i] [n] / A [i] [i];
}
}
}
for (int i = 0; i <n; i + +) X [i] = C [i];
float s = 0;
k = 0;
do
{
prov = 0;
for (int i = 0; i <n; i + +)
{
Y [i] = X [i];
for (int j = 0; j <n; j + +)
{
s + = B [i] [j] * X [i];
}
X [i] = s + C [i];
s = 0;
}
for (int i = 0; i <n; i + +)
{
if (fabs (X [i] - Y [i]) <e) prov + +;
}
k + +;
}
while (prov! = n);
Memo1-> Lines-> Add (»МЕТОД Якоб »);
Memo1-> Lines-> Add («»);
String p = »»;
Memo1-> Lines-> Add («Проміжна матриця:»);
for (int i = 0; i <n; i + +)
{
p = »»;
for (int j = 0; j <n +1; j + +)
{
p + = FloatToStr (B [i] [j ])+»»;
}
Memo1-> Lines-> Add (p);
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Коріння СЛАР рівні: »);
for (int i = 0; i <n; i + +)
{
if (X [i]! = NULL)
{
Memo1-> Lines-> Add («x» + IntToStr (i +1) + »=« + FloatToStr (X [i]));
}
else
{
Memo1-> Lines-> Add («Ні коренів! »);
break;
}
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Кількість ітерацій = «+ FloatToStr (k));
}
}
/ / -
void __fastcall TForm1: ButtonExitClick (TObject * Sender)
{
Close ();
}
/ / -
void __fastcall TForm1: RadioButton2Click (TObject * Sender)
{
ButtonYakobi-> Visible = false;
ButtonZeydel-> Visible = true;
ButtonRelax-> Visible = false;
}
/ / -
void __fastcall TForm1: RadioButton1Click (TObject * Sender)
{
ButtonYakobi-> Visible = true;
ButtonZeydel-> Visible = false;
ButtonRelax-> Visible = false;
}
/ / -
void __fastcall TForm1: ButtonZeydelClick (TObject * Sender)
{
Memo1-> Lines-> Clear ();
k = 0;
e = StrToFloat (Edit2-> Text);
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
TryStrToFloat (StringGrid1-> Cells [j] [i], A [i] [j]);
}
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
if (A [i] [j] == NULL)
{
ShowMessage («Помилка! Є порожні клітинки!");
fl1 = true;
i = n;
break;
}
}
}
if (! fl1) {
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
if (i! = j) B [i] [j] = (-1) * A [i] [j] / A [i] [i];
else
{
B [i] [j] = 0;
C [i] = A [i] [n] / A [i] [i];
}
}
}
for (int i = 0; i <n; i + +)
{
X [i] = rand ();
}
k = 0;
float s = 0;
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
s + = B [i] [j];
}
Y [i] = s;
s = 0;
}
s = Y [0];
for (int i = 1; i <n; i + +)
{
if (s <Y [i]) s = Y [i];
Y [i] = 0;
}
if (s <1)
{
do
{
s = 0;
for (int i = 0; i <n; i + +)
{
Y [i] = X [i];
}
for (int i = 0; i <n; i + +)
{
s = C [i];
for (int j = 0; j <n; j + +)
{
s + = X [j] * B [i] [j];
}
X [i] = s;
}
prov = 0;
for (int i = 0; i <n; i + +)
{
if (fabs (X [i] - Y [i]) <e) prov + +;
}
k + +;
}
while (prov! = n);
Memo1-> Lines-> Add (»МЕТОД Зейделя »);
Memo1-> Lines-> Add («»);
String p = »»;
Memo1-> Lines-> Add («Проміжна матриця:»);
for (int i = 0; i <n; i + +)
{
p = »»;
for (int j = 0; j <n +1; j + +)
{
p + = FloatToStr (B [i] [j ])+»»;
}
Memo1-> Lines-> Add (p);
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Коріння СЛАР рівні: »);
for (int i = 0; i <n; i + +)
{
if (X [i]! = NULL)
{
Memo1-> Lines-> Add («x» + IntToStr (i +1) + »=« + FloatToStr (X [i]));
}
else
{
Memo1-> Lines-> Add («Ні коренів! »);
break;
}
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Кількість ітерацій = «+ FloatToStr (k));
}
else {Memo1-> Lines-> Add («СЛАР є не збіжності !»);}
}
}
/ / -
void __fastcall TForm1: RadioButton3Click (TObject * Sender)
{
ButtonYakobi-> Visible = false;
ButtonZeydel-> Visible = false;
ButtonRelax-> Visible = true;
}
/ / -
void __fastcall TForm1: ButtonRelaxClick (TObject * Sender)
{
/ / TryStrToFloat (Edit2-> Text, e);
v_sh = StrToFloat (Edit3-> Text);
e = StrToFloat (Edit2-> Text);
Memo1-> Lines-> Clear ();
k = 0;
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
TryStrToFloat (StringGrid1-> Cells [j] [i], A [i] [j]);
}
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
if (A [i] [j] == NULL)
{
ShowMessage («Помилка! Є порожні клітинки!");
fl1 = true;
i = n;
break;
}
}
}
if (! fl1) {
float vsp = 0, alp = 0;
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
if (i! = j) B [i] [j] = (-1) * A [i] [j] / A [i] [i];
else
{
B [i] [j] = 0;
C [i] = A [i] [n] / A [i] [i];
}
}
}
float * sq_z = new float [n];
float * sq_y = new float [n];
for (int i = 0; i <n; i + +)
{
sq_z [i] = rand ();
}
for (int i = 0; i <n; i + +) sq_y [i] = C [i];
for (int i = 0; i <n; i + +) X [i] = 0;
vsp = C [0];
for (int j = 0; j <n; j + +)
{
vsp + = sq_z [j] * B [0] [j];
}
sq_z [0] = vsp;
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
vsp + = B [i] [j];
}
Y [i] = vsp;
vsp = 0;
}
vsp = Y [0];
for (int i = 1; i <n; i + +)
{
if (vsp <Y [i]) vsp = Y [i];
Y [i] = 0;
}
if (vsp <1)
{
do
{
for (int i = 0; i <n; i + +)
{
Y [i] = X [i];
}
for (int i = 0; i <n; i + +)
{
vsp = C [i];
for (int j = 0; j <n; j + +)
{
vsp + = sq_z [j] * B [i] [j];
alp + = B [i] [j] * sq_y [i];
}
sq_z [i] = vsp;
sq_y [i] = alp + C [i];
vsp = 0;
alp = 0;
X [i] = v_sh * sq_z [i] + (1-v_sh) * sq_y [i];
}
prov = 0;
for (int i = 0; i <n; i + +)
{
if (fabs (X [i] - Y [i]) <e) prov + +;
}
k + +;
}
while (prov! = n);
Memo1-> Lines-> Add (»МЕТОД ВЕРХНЬОЇ РЕЛАКСАЦІЇ »);
Memo1-> Lines-> Add («»);
String p = »»;
Memo1-> Lines-> Add («Проміжна матриця:»);
for (int i = 0; i <n; i + +)
{
p = »»;
for (int j = 0; j <n +1; j + +)
{
p + = FloatToStr (B [i] [j ])+»»;
}
Memo1-> Lines-> Add (p);
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Коріння СЛАР рівні: »);
for (int i = 0; i <n; i + +)
{
if (X [i]! = NULL)
{
Memo1-> Lines-> Add («x» + IntToStr (i +1) + »=« + FloatToStr (X [i]));
}
else
{
Memo1-> Lines-> Add («Ні коренів! »);
break;
}
}
Memo1-> Lines-> Add («»);
Memo1-> Lines-> Add («Кількість ітерацій = «+ FloatToStr (k));
}
else {Memo1-> Lines-> Add («СЛАР є не збіжності !»);}
}
}
/ / -
Результати розрахунку

Метод Якобі	Метод Зейделя	МЕТОД ВЕРХНЬОЇ РЕЛАКСАЦІЇ
Проміжна матриця: 0 -0,100000001490 -0,100000001490 0 -0,200000002980 0 -0,100000001490 0 -0,200000002980 -0,200000002980 0 0 Коріння СЛАР рівні: x1 = 1 x2 = 1 x3 = 1,00000011920929 Кількість ітерацій = 16	Проміжна матриця: 0 -0,100000001490 -0,100000001490 0 -0,200000002980 0 -0,100000001490 0 -0,200000002980 -0,200000002980 0 0 Коріння СЛАР рівні: x1 = 1 x2 = 0,99999988079071 x3 = 0,999999940395355 Кількість ітерацій = 9	Проміжна матриця: 0 -0,100000001490 -0,100000001490 0 -0,200000002980 0 -0,100000001490 0 -0,200000002980 -0,200000002980 0 0 Коріння СЛАР рівні: x1 = 1,00000011920929 x2 = 0,99999988079071 x3 = 0,999999940395355 w = 1 Кількість ітерацій = 9